package 动态规划;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * 完全背包问题
 *  一个旅行者有一个最多能装m公斤的背包，现有n件物品，它们的重量分别是W1,W2...,Wn它们的价值分别是C1,C2...Cn,求旅行者能获得的最大总价值(每个物品可以反复拿)
 * 递归思路：
 *  当有 nums.length 个物品，物品的重量为nums.w,价值为nums.c
 *      f(n)表示容量为n时，在这些商品中最多能取到的的值
 *  f(n)无法直接给出答案，但如果 能给出最后一件
 * 选择物品1时的最大值f(n-nums[1].w)+nums[1].c，选择物品2时的最大值f(n-nums[2].w)+nums[2].c,..选择物品nums.length时的最大值f(n-nums[length].w)+nums[length].c，
 * 那么f(n)可以通过比较 nums[1]到nums[length] 确定最后一件该选什么 即我们需要给出 f(n-最后一件的重量)的最大值
 *      f(n-最后一件的重量)：也无法直接得出 也需要像f(n)一样 ，需要有人给出 f(n- 最后一件 - 倒数第二件)的最大值，然后通过 倒数第二件来确定倒数第一件 是哪一件
 *      直到无法选择任何一件时 f(n<任何一件物品的重量): 返回 0
 *  即：f(n)=max(f(n-nums[1].w)+nums[1].c , f(n-nums[2].w)+nums[2].c , ... ,f(n-nums[length].w)+nums[length].c)，
 */
public class Ch06_完全背包问题递归 {

    public static void main(String[] args) {
        int[] w={2,3,4,7};   //重量
        int[] c={1,3,5,9}; //价值
        int capacity=100;
//        Scanner sc=new Scanner(System.in);
//        int capacity=sc.nextInt();
//        int n=sc.nextInt();
//        int[]w=new int[n],c=new int[n];
//        for(int i=0;i<n;i++) {
//            w[i]=sc.nextInt();
//            c[i]=sc.nextInt();
//        }
        System.out.println(maxKnapsack(w, c, capacity));
    }
    public static Map<Integer,Integer> map=new HashMap();

    /**
     * 返回 容量为capacity时，在这些物品中能取到的最大值
     * @param w：物品重量
     * @param c：物品价值
     * @param capacity：容量
     * @return
     */
    public static int maxKnapsack(int[] w,int[] c,int capacity){
        if (map.containsKey(capacity)){
            return map.get(capacity);
        }
        if (capacity<=0){
            return 0;
        }
        //获取最后选择某一物品时能获得的最大价值
        int[] select=new int[w.length];
        for (int i=0;i<w.length;i++){
            if (capacity>=w[i]){
//                maxKnapsack(w,c,capacity-w[i]) :表示 拿 物品i之前的 容量 能拿到的最大价值
                select[i]=maxKnapsack(w,c,capacity-w[i])+c[i];
//                select[i]表示最后一件选择物品 i 能拿到的最大价值
            }
        }
        int max = max(select);
        map.put(capacity,max);
        return max;
    }
    public static int max(int[] nums){
        if (nums==null||nums.length==0){
            return 0;
        }
        int max=0;
        for (int num : nums) {
            if (num>max){
                max=num;
            }
        }
        return max;
    }
}
